package MiddlePractice;


import java.util.LinkedList;
import java.util.List;

import util.TreeNode;


class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode p = root;
		TreeNode r = null;
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		List<Integer> list  = new LinkedList<Integer>();
		while(p != null || !stack.isEmpty()) {
			if(p != null) {
				stack.addLast(p);
				p = p.left;
			}
			else {
				p = stack.peekLast();
				if(p.right != null && p.right != r)
					p = p.right;
				else {
					p = stack.removeLast();
					list.add(p.val);
					r = p;
					p = null;
				}
			}
		}
		return list;
    }
}


public class Demo145 {
	public static void main(String[] args) {
		TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
		List<Integer> list = new Solution().postorderTraversal(root);
		for(Integer i:list)
			System.out.println(i);
		System.out.println("end");
	}
}
